import java.util.Arrays;

public class Solution1042 {
    public int[] gardenNoAdj(int n, int[][] paths) {
        int[] first=new int[n];
        Arrays.fill(first,-1);
        int c=0;
        int[] next=new int[paths.length*2];
        int[] go=new int[paths.length*2];
        for (int[] path : paths) {
            next[c]=first[path[0]-1];
            go[c]=path[1]-1;
            first[path[0]-1]=c;
            c++;
            next[c]=first[path[1]-1];
            go[c]=path[0]-1;
            first[path[1]-1]=c;
            c++;
        }
        int[] visit=new int[n];
        for (int i=0;i<n;i++){
            int[] f=new int[5];
            int p=first[i];
            while (p!=-1){
                f[visit[go[p]]]++;
                p=next[p];
            }
            for (int j=1;j<=4;j++){
                if (f[j]==0){
                    visit[i]=j;
                    break;
                }
            }
        }
        return visit;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1042().gardenNoAdj(4, new int[][]{{1, 2}, {3, 4}})));
    }
}
